﻿#pragma once
#include "FormatedUtil.h"
#include "Index.h"
class IReorderArray2
{
public:
	/**
	 * 调整数组顺序使奇数位于偶数前面(二).
	 * https://www.nowcoder.com/practice/0c1b486d987b4269b398fee374584fc8?tpId=265&tqId=39274&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D2%26tpId%3D13%26type%3D265&difficulty=undefined&judgeStatus=undefined&tags=&title=
	 *
	 * 输入一个长度为 n 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，
	 * 使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，
	 * 但是时间复杂度和空间复杂度必须如下要求。
	 *
	 * 数据范围：0≤n≤50000，数组中每个数的值0≤val≤10000
	 * 要求：时间复杂度O(n)，空间复杂度O(1)
	 */
	virtual std::vector<int> ReorderArray2(std::vector<int>& array) = 0;
};

class ReorderArray2
{
public:
	class Solution :public IReorderArray2
	{
	public:
		std::vector<int> ReorderArray2(std::vector<int>& array) override
		{
			if (array.empty())
				return {};
			const int arrSize = array.size();

			int oddIndex = -1;
			int evenIndex = arrSize;
			for (int i = 0; i < arrSize; ++i)
			{
				//当迭代的索引和后面偶数的索引指向同一处时，奇数就已经全部排序在偶数前面了
				if (i == evenIndex)
					break;
				//为偶数
				while ((array[i] & 0x1) == 0)
				{
					evenIndex--;
					std::swap(array[i], array[evenIndex]);
					if (i == evenIndex)
						return array;
				}
				//array[i]为奇数
				oddIndex++;
			}
			return array;
		}
	};
public:
	class Review1:public IReorderArray2
	{
	public:
		std::vector<int> ReorderArray2(std::vector<int>& array) override
		{
			if (array.empty())
				return {};

			const int arrSize = array.size();
			int evenIndex = arrSize;
			for (int i = 0; i < arrSize; ++i)
			{
				//当array[i]为偶数时，不停地与后面的evenIndex的位置交换
				while (i < evenIndex && (array[i] & 0x1) == 0)
				{
					std::swap(array[i], array[--evenIndex]);
				}
			}
			return array;
		}
	};
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
class ReorderArray2Test :public SolutionTestor<IReorderArray2>
{
protected:
	void LoadSolutions(std::vector<IReorderArray2*>& solutions) override
	{
		solutions = {
			new ReorderArray2::Solution,
			new ReorderArray2::Review1,
		};
	}
};
TEST_F(ReorderArray2Test, ReorderArray2)
{
	TestForSolutions([](IReorderArray2* solution) 
	{
		std::vector<String> testSamples = {
	"[1,2,3,4]",
	"[1,3,7,9]",
	"[2,4,6,8]",
	"[1,4,4,5,4,4,3]"
		};
		auto randNums = TestingUtil::randSizedInts(500, 1000);
		testSamples.emplace_back(FormatedUtil::dumpFormated(randNums));

		for (auto& input : testSamples)
		{
			std::vector<int> nums;
			FormatedUtil::parseFormated(nums, input);

			std::vector<int> array = nums;
			auto reorderedNums = solution->ReorderArray2(array);

			//重排后的数组长度没有变化
			EXPECT_EQ(reorderedNums.size(), nums.size());
			//重排后的数组的元素在原先的数组中存在
			for (auto& num : reorderedNums)
				EXPECT_TRUE(std::find(nums.begin(), nums.end(), num) != nums.end());
			//重排后的数组奇数元素都在偶数元素前面
			{
				//找到首个偶数的索引
				const int numsSize = reorderedNums.size();
				int firstEvenIndex = numsSize;
				for (int i = 0; i < numsSize; ++i)
				{
					if ((reorderedNums[i] % 2) == 0)
					{
						firstEvenIndex = i;
						break;
					}
				}

				//奇数元素的索引范围在[0,firstEventIndex)
				//偶数元素的索引范围在[firstEventIndex,numsSize)
				for (int i = 0; i < numsSize; ++i)
				{
					if (reorderedNums[i] % 2 == 0)
						EXPECT_TRUE(i >= firstEvenIndex && i < numsSize);
					else
						EXPECT_TRUE(i >= 0 && i < firstEvenIndex);
				}
			}
		}
		});
}
#endif
